//堆这个数据结构是在数组上存储的完全二叉树
//堆的操作最重要的就是两个heapInsert heapify，
//heapInsert即添加一个数到最后的位置，我们将其向上调整为堆
//heapify就是有一个数据在堆中，我们能否向下调整为堆结构
//说白了就是向上调整和向下调整
//那么在任意位置删除一个元素就是和最后一个元素交换，然后heapSize--
//，判断这两个数谁大，假设原来最后一个元素大我们就向上调整，否则向下
//改变一个元素，调整堆结构，和删除任意位置的一个数相同操作

//将一个数组调整为堆的两个重要过程
//arr = [num1, num2, num3 .......];
void heapInsert(vector<int>& arr, int index)//任意位置向上调整
{
	if (index >= arr.size())
	{
		return ;
	}
	//index位置处的父节点为 index - 1 / 2
	int father = (index - 1) / 2;
	while (father >= 0 && arr[father] < arr[index])
	{
		int temp = arr[father];
		arr[father] = arr[index];
		arr[index] = temp;
		index = father;
		father = (index - 1) / 2;
	}
}

void heapIfy(vector<int>& arr, int index, int heapSize) //任意位置向下调整，到heapSize为止
{
	if (index >= heapSize)
	{
		return ;
	}
	int leftchild = 2 * index + 1;
	while (leftchild < heapSize)
	{
		int idx;//idx记录父节点以及两个子节点最大的那个下标
		idx = (leftchild + 1 < heapSize) ? 
			(arr[leftchild + 1] > arr[leftchild] ? leftchild + 1 : leftchild): leftchild;
		idx = arr[idx] > arr[index] ? idx : index;
		if (index == idx)
		{
			break;
		}
		int temp = arr[index];
		arr[index] = arr[idx];
		arr[idx] = temp;
		index = idx;
		leftchild = 2 * idx + 1;
	}
}